package com.lw.leetcode.dp.c;

/**
 * Created with IntelliJ IDEA.
 * 1745. 回文串分割 IV
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/30 10:38
 */
public class CheckPartitioning {

    public static void main(String[] args) {
        CheckPartitioning test = new CheckPartitioning();

        // true
//        String str = "abcbdd";

        // false
        String str = "abcd";

        boolean b = test.checkPartitioning(str);
        System.out.println(b);
    }

    public boolean checkPartitioning(String s) {
        char[] chars = s.toCharArray();
        int length = s.length();
        int[][] items = new int[length][length];
        for (int i = length - 1; i >= 0; i--) {
            items[i][i] = 1;
            for (int j = i + 1; j < length; j++) {
                if (chars[i] == chars[j] && (i + 1 == j || i + 2 == j || items[i + 1][j - 1] == 1)) {
                    items[i][j] = 1;
                }
            }
        }
        for (int i = 0; i < length - 2; i++) {
            for (int j = i + 1; j < length - 1; j++) {
                if (items[0][i] == 1 && items[i + 1][j] == 1 && items[j + 1][length - 1] == 1) {
                    return true;
                }
            }
        }
        return false;
    }

}
